package com.lw.leetcode.str.b;

/**
 * Created with IntelliJ IDEA.
 * b
 * str
 * 1910. 删除一个字符串中所有出现的给定子字符串
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/6 18:18
 */
public class RemoveOccurrences {


    public static void main(String[] args) {
        RemoveOccurrences test = new RemoveOccurrences();

        // dab
        String a = "daabcbaabcbc";
        String b = "abc";

        // ab
//        String a = "axxxxyyyyb";
//        String b = "xy";

        // 输入：s = "axxxxyyyyb", part = "xy"
        //输出："ab"

        String s = test.removeOccurrences(a, b);
        System.out.println(s);
    }


    private int n;
    private char[] chars;
    private int[] ints;

    public String removeOccurrences(String s, String part) {
        this.n = part.length();
        this.chars = part.toCharArray();
        this.ints = find();
        while (true) {
            int length = s.length();
            s = find(s);
            if (s.length() == length) {
                return s;
            }
        }
    }

    private String find(String a) {
        int m = a.length();
        if (m < n) {
            return a;
        }
        int i = 0;
        int j = 0;
        while (i < m && j < n) {
            if (j == -1 || a.charAt(i) == chars[j]) {
                i++;
                j++;
            } else {
                j = ints[j];
            }
        }
        if (j == n) {
            return a.substring(0, i - j) + a.substring(i);
        } else {
            return a;
        }
    }

    private int[] find() {
        int[] arr = new int[n];
        arr[0] = -1;
        int j = -1;
        int i = 0;
        while (i < n - 1) {
            if (j == -1 || chars[i] == chars[j]) {
                i++;
                j++;
                arr[i] = j;
            } else {
                j = arr[j];
            }
        }
        return arr;
    }

}
